/**
 * 63. Unique Paths II 不同的路径 II
 * https://leetcode-cn.com/problems/unique-paths-ii/
 */
class UniquePathsII {
    /**
     * 方法：动态规划
     * 
     * Args:
     *   obstacleGrid: 二维数组,表示网格。1表示障碍物,0表示空位
     * 
     * Returns:
     *   从左上角到右下角的不同路径数量
     * 
     * Time: O(m*n), m和n分别是网格的行数和列数
     * 
     * Space: O(n), 只使用一个一维数组记录状态
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid[0].length;
        int[] f = new int[n+1];
        f[1] = 1;
        for(int[] row : obstacleGrid){
            for(int j = 0; j < n; j++){
                if(row[j] == 0){
                    f[j+1] += f[j];
                }else{
                    f[j+1] = 0;
                }
            }
        }
        return f[n];
    }
}